package dp;

/**
 * @author Liaorun
 */
public class CoinsMin {
    public static void main(String[] args) {
        int len = 10;
        int max = 10;
        int testTime = 10000;

        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(len, max);

            int aim = (int) (Math.random() * 3 * max) + max;

            if (getLessCoinCount(arr, aim) != minCoins1(arr, aim)) {
                System.out.println("ooops");
                break;
            }
        }
    }

    private static int[] generateRandomArray(int len, int max) {
        int[] arr = new int[(int) (Math.random() * len) + 1];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) + 1;
        }
        return arr;
    }

    public static int getLessCoinCount(int[] arr, int aim) {
        int[][] dp = new int[arr.length + 1][aim + 1];


        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = -2;
            }
        }

        System.out.println(dp[0][0]);

        // 从第一个硬币开始尝试拿
        return f(arr, 0, aim, dp);
    }

    /**
     * @param arr   硬币都在其中，固定参数
     * @param index 拿硬币的开始位置
     * @param dp    计算结果缓存
     * @return
     */
    private static int f(int[] arr, int index, int rest, int[][] dp) {

        if (rest < 0) {
            return -1;
        }

        // 其他尝试的分支已经计算过这种情况
        // 相当于人类使用前辈的经验，可以走的更快，相当于缓存的书籍
        if (dp[index][rest] != -2) {
            return dp[index][rest];
        }

        if (rest == 0) {
            dp[index][rest] = 0;
            return 0;
        }

        if (index == arr.length) {
            dp[index][rest] = -1;
            return -1;
        }
        int p1 = f(arr, index + 1, rest, dp);
        int p2 = f(arr, index + 1, rest - arr[index], dp);

        if (p1 == -1 && p2 == -1) {
            // 没有有效尝试
            dp[index][rest] = -1;
            return -1;
        } else {
            if (p1 == -1) {
                // 要当前硬币，数量要+1
                dp[index][rest] = p2 + 1;
                return p2 + 1;
            } else if (p2 == -1) {
                dp[index][rest] = p1;
                return p1;
            } else {
                // 两个有效尝试，选更好的，硬币更少的
                dp[index][rest] = Math.min(p1, p2);
                return Math.min(p1, p2);
            }
        }
    }

    public static int minCoins1(int[] arr, int aim) {
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];

        // 0行的数据全为0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        // n列除了第0行全为-1
        for (int i = 1; i <= aim; i++) {
            dp[n][i] = -1;
        }

        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 1; rest <= aim; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = -1;
                if (rest - arr[index] >= 0) {
                    p2 = dp[index + 1][rest - arr[index]];
                }

                if (p1 == -1 && p2 == -1) {
                    // 没有有效尝试
                    dp[index][rest] = -1;
                } else {
                    if (p1 == -1) {
                        // 要当前硬币，数量要+1
                        dp[index][rest] = p2 + 1;
                    } else if (p2 == -1) {
                        dp[index][rest] = p1;
                    } else {
                        // 两个有效尝试，选更好的，硬币更少的
                        dp[index][rest] = Math.min(p1, p2);
                    }
                }
            }
        }
        return dp[0][aim];
    }
}
